/**
https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/
429. N 叉树的层序遍历
 Medium, 方钊堉 2024.12.07
 BFS
 */

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        // 如果根节点为空，返回空的结果集
        if (!root) return {};

        vector<vector<int>> levels; // 存储每层节点值的二维数组
        queue<Node*> nodesQueue; // 用于层次遍历的队列
        nodesQueue.push(root); // 将根节点加入队列

        while (!nodesQueue.empty()) {
            int levelSize = nodesQueue.size(); // 当前层的节点数量
            vector<int> currentLevel; // 存储当前层的节点值

            // 遍历当前层的所有节点
            for (int i = 0; i < levelSize; ++i) {
                Node* currentNode = nodesQueue.front(); // 获取队列中的第一个节点
                nodesQueue.pop(); // 移除队列中的第一个节点
                currentLevel.push_back(currentNode->val); // 将节点值加入当前层的结果

                // 将当前节点的所有子节点加入队列
                for (auto& child : currentNode->children) {
                    nodesQueue.push(child);
                }
            }

            // 将当前层的结果加入最终结果集中
            levels.push_back(currentLevel);
        }

        return levels;
    }
};